Virtual private networks (VPN) typically involves an agreement between two private networks, separated by a public network (e.g., the Internet), to encode data packets, such as Internet Protocol (IP) packets, transmitted between them via the public network. The connection between the two private networks over the public network is often referred to as a VPN tunnel (also known as a VPN connection). A given private network may have multiple VPN tunnels to other networks. The configuration that determines what data is encoded and over what path the data is transmitted is referred to as a security association (SA) of the VPN tunnel on which that data is to be transmitted.
Since there can be multiple VPN tunnels established by different sending devices to a receiving device and each VPN tunnel may have a different SA, a unique tunnel index is assigned to each VPN tunnel in general. In particular, the SA is negotiated between a sending device in one of the two private networks and a receiving device in the other private network. Different VPN tunnels may or may not have the same SA. During the negotiation, the receiving device typically picks a random number to be a tunnel index, such as a security parameter index (SPI) to identify the SA of the VPN tunnel through which the data packets are transported; each data packet transmitted on a VPN tunnel, includes the SPI of that VPN tunnel. When a number of VPN tunnels have been established to send packets to a given device, that device may use the SPI in each data packet received to identify the corresponding SA for the data packet. Based on the SA identified, the receiving device may decode the data packet correctly.
FIG. 1 illustrates one conventional VPN system. The system 100 includes two private networks 101 and 102, two firewalls 110 and 120, and a VPN tunnel 140. The private network 101 is coupled to the firewall 110 such that the communication between devices (e.g., personal computers, servers, clients, Voice-over-Internet Protocol telephones, etc.) within the private network 101 and devices (e.g., personal computers, servers, clients, Voice-over-Internet Protocol telephones, firewalls, etc.) outside of the private network 101 goes through the firewall 110. Likewise, the private network 102 is coupled to the firewall 120 such that the communication between devices (e.g., personal computers, servers, clients, Voice-over-Internet Protocol telephones, etc.) within the VPN 102 and devices (e.g., personal computers, servers, clients, Voice-over-Internet Protocol telephones, firewalls, etc.) outside of the private network 102 goes through the firewall 120. The VPN tunnel 140 coupled the firewall 110 and the firewall 120 over a public network 130, such as the Internet.
Note that any or all of the components and the associated hardware illustrated in FIG. 1 may be used in various embodiments of the system 100. However, it should be appreciated that other configurations of the system 100 may include more, less, or different devices than those shown in FIG. 1.
Communication between the private networks 101 and 102 may not be secure because data packets (e.g., IP packets) are transmitted across the public network 130 to reach the other private network and the data packets may be intercepted by an unauthorized party over the Internet 130. Therefore, the VPN tunnel 140 is established between the firewalls 110 and 120 to provide a more secure medium for data packet transmission between the firewalls 110 and 120. In some embodiments, data packets entering the VPN tunnel 140 are encoded by the transmitting firewall and decoded by the receiving firewall. Note that the VPN tunnel 140 is bi-directional. Thus, the VPN tunnel 140 provides a secure way for the devices within the private networks 101 and 102 to communicate with each other over the public network 130.
While only one VPN tunnel 140 is shown in FIG. 1 to simplify the illustration, one should appreciate that there can be multiple VPN tunnels established between a given firewall (e.g., 110 or 120) and additional firewalls and/or devices, where these additional firewalls and/or devices may or may not be within the same private network. Therefore, a unique tunnel index is assigned to each VPN tunnel established. In particular, when the VPN tunnel 140 is established, the sending device in the sending private network (e.g., private network 101 or 102) may negotiate with the receiving device in the receiving private network (e.g., private network 102 or 101) to come up with the SA of the VPN tunnel 140. During the negotiation, the receiving device also selects a tunnel index to be included in every data packet transmitted via the VPN tunnel 140 to identify the SA of the VPN tunnel 140. The tunnel index selected may be a Security Parameter Index (SPI).
Using the tunnel index in a data packet received, the receiving firewall may identify the VPN tunnel 140 via which the data packet is transported, and hence, the SA associated with the VPN tunnel 140. Based on the SA, the receiving firewall and/or the receiving device in the receiving private network may decode the data packet received.
Currently, one way to look up a SA of a VPN tunnel is to perform a regular list walk of a list storing the tunnel indices and the SAs, such as the Security Association Database (SADB) list. One problem with this technique is that the list walk is not scalable. The SADB list walk has to be performed for every packet received. As the number of SAs grows in the order of thousands, the list walk may require walking through thousands of entries in the SADB before finding the correct SA. Thus, the list walk may become too time-consuming, and hence, slow down network traffic between the private networks.